While video and television are well known to represent a significant proportion of traffic in the next few years, there exists a disconnect between what the network planners envisage and what the users expect. The demand for High Definition (HD) video is increasing faster than the bandwidth deployment. In addition, convergence of telecommunications and entertainment services create new requirements from quality of service (QoS) to mobility that stress the limits of existing networks. The industry is just starting to awake to the new realities of multi-screen, multi-network and multimedia experiences. This new reality is also reflected by the massive migration of video content from the traditional broadcast media to the Internet with Internet Protocol Television (IPTV), IP video and mobile TV becoming more and more almost interchangeable. While a lot of work has been done on controlling the next generation networks, as illustrated by the development of the Internet Multimedia Subsystem (IMS), little has been done to alleviate the transmission of the data itself. People are mobile, not just devices, and they watch video on an ever-growing ecosystem of computers and portable devices. These range from personal computers (PCs) and laptops, to a wide variety of mobile devices and phone with features different from traditional set-top boxes (STBs) connected to TVs. Further, the new realities of Social TV ensure that often more than one of these devices will be used at the same time for an enhanced viewing experience.
In addition to mobile TV and social TV, many other real-time applications, such as teleconferencing, and distance learning, require multicast from a single source to multiple receivers. In conventional multicasts, all receivers receive at the same rate. In practice, however, receivers can have widely different characteristics. It becomes desirable to serve each receiver at a rate commensurate with its own demand and capability. One approach to multirate multicast is to use multi-description codes (MDC), dividing source data into equally important streams such that the decoding quality using any subset of the streams is acceptable, and better quality is obtained by more descriptions. A popular way to perform MDC is to combine layered coding with the unequal error protection of a priority encoding transmission (PET) system. Another approach for multirate multicast is to use multi-resolution codes (MRC), encoding data into a base layer and one or more refinement layers. Receivers subscribe to the layers cumulatively, with the layers incrementally combined at the receivers to provide progressive refinement. The decoding of a higher layer always requires the correct reception of all lower layers including the base layer.
The present invention provides multirate multicast with random linear network coding and demand-pushback from the receivers to the source. Network coding allows and encourages mixing of data at intermediate nodes. It has been shown that for a single rate multicast, network coding achieves the minimum of the maximum flow to each receiver; this limit is generally not achievable through traditional routing schemes. For multirate multicast with a total of n-layers to transmit at the source, linear network codes can satisfy requests from all the receivers if the n layers are to be multicasted to all but one receiver. If more than one subscribe to subsets of the n-layers, linear codes cease to be sufficient for layered multicast.
Previous work on multirate multicast with network coding includes the MDC approach, wherein modified PET at the source is catered for network coded systems. Recovery of some layers is guaranteed before full rank linear combinations of all layers are received, and this is achieved at the cost of a lower code rate. Others have studied the problem of Rainbow Network Coding, which incorporates linear network coding into multi-description coded multicast. Still others have studied multi-resolution media streaming, and proposed a polynomial-time algorithm for multicast to heterogeneous receivers. Others have considered multirate multicast in overlay networks, organizing receivers into layered data distribution meshes, and utilizing network coding in each mesh. Yet still others have proposed the Layered Separated Network Coding Scheme to maximize the total number of layers received by all receivers.
In all the previous work, the aggregate rate to all receivers is maximized by solving the linear network coding problem separately for each layer. Specifically, for each layer, a subgraph is selected for network coding by performing linear programming. In other words, only intra-layer network coding is allowed. On the other hand, inter-layer network coding, which allows coding across layers, often achieves higher throughput. Incorporating inter-layer linear network coding into multirate multicast, however, is significantly more difficult, as intermediate nodes have to know the network topology and the demands of all down-stream receivers before determining its network codes.
Others have considered inter-layer network coding by performing integer-programming (IP) flow optimization on “multicast layers i” defined as the combinations of layers from 1 up to i. In addition to IP, which is NP-Hard, this algorithm requires several computations of edge disjoint paths, which are also NP-Hard. It also requires centralized knowledge of the network topology. Such centralized algorithms are difficult to perform on general networks.